package org.example.myleet.p488;

import java.util.*;

/**
 * 官方解
 * https://leetcode-cn.com/problems/zuma-game/solution/zu-ma-you-xi-by-leetcode-solution-lrp4/
 */
public class Solution {

    static class Situation {
        String board;
        String hand;

        public Situation(String board, String hand) {
            this.board = board;
            this.hand = hand;
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            Situation situation = (Situation) o;
            return Objects.equals(board, situation.board) &&
                    Objects.equals(hand, situation.hand);
        }

        @Override
        public int hashCode() {
            return Objects.hash(board, hand);
        }
    }

    public int findMinStep(String board, String hand) {
        int[] boardBallCount = new int[26];
        int[] handBallCount = new int[26];
        for (char c : board.toCharArray()) {
            ++boardBallCount[c - 'A'];
        }
        char[] handCharArr = hand.toCharArray();
        for (char c : hand.toCharArray()) {
            ++handBallCount[c - 'A'];
        }
        Arrays.sort(handCharArr);
        hand = new String(handCharArr);
        for (int i = 0; i < 26; ++i) {
            if (0 < boardBallCount[i] && boardBallCount[i] + handBallCount[i] < 3) {
                return -1;
            }
        }
        int opt = 0;
        HashSet<Situation> situations = new HashSet<>();
        Queue<Situation> queue = new LinkedList<>();
        queue.offer(new Situation(board, hand));
        while (!queue.isEmpty()) {
            int len = queue.size();
            for (int i = 0; i < len; ++i) {
                Situation situation = queue.poll();
                StringBuilder curBoard = new StringBuilder(situation.board);
                if (curBoard.length() == 0) {
                    return opt;
                }
                StringBuilder curHand = new StringBuilder(situation.hand);
                for (int j = 0; j < curHand.length(); ++j) {
                    char h = curHand.charAt(j);
                    curHand.deleteCharAt(j);
                    for (int k = 0; k <= curBoard.length(); ++k) {
                        if (k > 0) {
                            if (h == curBoard.charAt(k - 1)) {
                                continue;
                            }
                        }
                        curBoard.insert(k, h);
                        String newBoard = stabilize(curBoard).toString();
                        String newHand = curHand.toString();
                        Situation newSituation = new Situation(newBoard, newHand);
                        if (!situations.contains(newSituation)) {
                            situations.add(newSituation);
                            queue.offer(newSituation);
                        }
                        curBoard.deleteCharAt(k);
                    }
                    curHand.insert(j, h);
                }
            }
            ++opt;
        }
        return -1;
    }

    public StringBuilder stabilize(StringBuilder board) {
        Deque<Character> stack = new LinkedList<>();
        for (int i = 0; i < board.length(); ++i) {
            char c = board.charAt(i);
            if (stack.isEmpty() || stack.size() < 2) {
                stack.push(c);
            } else {
                if (c == stack.peek()) {
                    char top = stack.pop();
                    if (c == stack.peek()) {
                        stack.pop();
                        int nextI = i + 1;
                        while (nextI < board.length() && c == board.charAt(nextI)) {
                            ++i;
                            ++nextI;
                        }
                    } else {
                        stack.push(top);
                        stack.push(c);
                    }
                } else {
                    stack.push(c);
                }
            }
        }
        StringBuilder newBoard = new StringBuilder();
        while (!stack.isEmpty()) {
            newBoard.append(stack.pop());
        }
        return newBoard.reverse();
    }
}
